//
//  RadixSort.swift
//  Chapter3LinkedList
//
//  Created by TRS-Mobile on 2021/9/3.
//

import Foundation

//基数排序
extension Array where Element == Int {
    
    /// 基数排序
    mutating func radixSort() {
        let base = 10
        var done = false
        var digits = 1
        let des = ["个", "十", "百", "千", "万", "十万"]
        var idx = 0
        while !done {
            done = true
            var buckets: [[Element]] = .init(repeating: [], count: base)
            forEach { number in
                let remainingPart = number / digits
                let digit = remainingPart % base
                buckets[digit].append(number)
                if remainingPart > 0 {
                    done = false
                }
            }
            digits *= base
            self = buckets.flatMap { $0 }
            print("\(des[idx])-->: \(self)")
            idx += 1
        }
    }
}
